package main


// 直接模拟，求出来 天际线 水平竖直的。
func maxIncreaseKeepingSkyline(grid [][]int) int {
	// 竖向天际线
	colLine := make([]int, len(grid[0]))
	rowLine := make([]int, len(grid))
	for i, rows := range grid {
		maxV := rows[0]
		for _, c := range rows {
			maxV = max(maxV, c)
		}
		colLine[i] = maxV
	}
	// 横向天际线
	for j := 0; j < len(grid[0]);j++ {
		maxV := 0
		for _, rows := range grid {
			maxV = max(maxV, rows[j])
		}
		rowLine[j] = maxV
	}
	// 求能填多少
	rst := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			rst += min(rowLine[j], colLine[i]) - grid[i][j]
		}
	}
	return rst
}


func max(a,b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}


// 官方题解更简单， 两个天际线，一起求
func maxIncreaseKeepingSkyline1(grid [][]int) (ans int) {
	n := len(grid)
	rowMax := make([]int, n)
	colMax := make([]int, n)
	for i, row := range grid {
		for j, h := range row {
			rowMax[i] = max(rowMax[i], h)
			colMax[j] = max(colMax[j], h)
		}
	}
	for i, row := range grid {
		for j, h := range row {
			ans += min(rowMax[i], colMax[j]) - h
		}
	}
	return
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}




